/*
 * =====================================================================================
 *
 *       Filename:  countAB.cpp
 *
 *    Description:  From TopCoder 
 *
 *        Version:  1.0
 *        Created:  12/08/2010 03:44:37 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ken Chen (Ken), chen_kenz@emc.com
 *        Company:  EMC
 *
 * =====================================================================================
 */

#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <cassert>
#include <iostream>
using namespace std;

namespace Bad
{

vector<string> enumerateAB( int n )
{
  vector<string> abStrs;
  int k = ( 1 << n ) ;

  for( int i = 0; i < k; ++i )
  {
    string ab("");
    for( int pos = 0; pos < n; ++pos ) 
    {
      if( (1 << pos) & i )
      {
        ab.append("B");
      }
      else
      {
        ab.append("A");
      }
    }
    abStrs.push_back( ab );  
  }

  return abStrs;
}

string strToAB( const string& str )
{
  assert( !str.empty() && str.size() <= 26 );
  assert( str.find_first_not_of("abcdefghijklmnopqrstuvwxyz") == string::npos );

  int n = str.size();
  vector<int> index(n, 0);

  for( int i = 0; i < n; ++i )
  {
    index[str[i] - 'a'] = i; 
  }

  string AB("");
  for( int j = 0; j < n - 1; ++j )
  {
    if( index[j] < index[j+1] )
    {
      AB.append("A"); 
    }
    else
    {
      AB.append("B"); 
    }
  }

  return AB;
}

int countAB( const string& AB )
{
  assert( AB.find_first_not_of("AB") == string::npos );
  assert( AB.size() < 26 );

  int cnt = 0;
  string alphabet("abcdefghijklmnopqrstuvwxyz");
  string str( alphabet.substr(0, AB.size() + 1 ) );

  do
  {
    if( AB == strToAB( str ) ) 
    {
      ++cnt;
    }
  }while(next_permutation(str.begin(), str.end()));

  return cnt;
}

} // Bad

namespace Better
{

int countAB( const string& AB )
{
  assert( AB.find_first_not_of("AB") == string::npos );
  assert( AB.size() < 26 );

  int n = static_cast<int>( AB.size() ) + 1;
  vector<vector<int> > occurs( n, vector<int>(n, 0) );

  occurs[0][0] = 1;

  for( int i = 1; i < n ; ++i )
  {
    for( int pos = 0; pos < i; ++pos )
    {
      int first_pos = 0;
      int last_pos = 0;

      if( AB[i-1] == 'A' )
      {
        first_pos = pos + 1;
        last_pos = i; 
      }
      else
      {
        first_pos = 0;
        last_pos = pos;
      }

      int cnt = occurs[i-1][pos];
      for( ; first_pos <= last_pos; ++first_pos )
      {
        occurs[i][first_pos] += cnt;
      }
    }
  }

  return accumulate( occurs[n-1].begin(), occurs[n-1].end(), 0 );
}

} // Better


int main( int argc, char* argv[] )
{
  cout << Better::countAB("A") << endl;
  cout << Better::countAB("B") << endl;
  cout << Better::countAB("ABBAA") << endl;

  cout << Bad::countAB("A") << endl;
  cout << Bad::countAB("B") << endl;
  cout << Bad::countAB("ABBAA") << endl;

  return 0;
}

